#ifndef _INTERPRET_H_
#define _INTERPRET_H_
#include <vector>
#include <set>
#include "util.h"
#include "objects.h"
#include "allocator.h"

const uint64 kVarHashSize = (1 << 20);
const uint64 kVarHashMask = (1 << 20) - 1;

#define SavedObject(name) Object *name = NULL; ObjectSaver s_##name(a_, &name); name 
#define SavedObjectVector(name) vector<Object *> name; ObjectVectorSaver s_##name(a_, &name)

// All native function enums
enum NativeFunction {
  NATIVE_INT_CHAR,
  NATIVE_CHAR_INT,
  NATIVE_PLUS, 
  NATIVE_MINUS,
  NATIVE_TIMES,
  NATIVE_MOD,
  NATIVE_DIVIDE,
  NATIVE_EQUAL,
  NATIVE_LESS,
  NATIVE_NOT,
  NATIVE_FUNCALL,
  NATIVE_SYSCALL,
  NATIVE_HLESS,
  NATIVE_HASH,
  NATIVE_HASH60,
  NATIVE_LIST,
  NATIVE_ARRAY,
  NATIVE_MARRAY,
  NATIVE_ARRAYP,
  NATIVE_BREF,
  NATIVE_MMAP,
  NATIVE_INTEGERP,
  NATIVE_CHARP,
  NATIVE_SYMBOLP,
  NATIVE_NATIVEP,
  NATIVE_SPECIALP,
  NATIVE_GLOBALP,
  NATIVE_AREF,
  NATIVE_MSET,
  NATIVE_LENGTH,
  NATIVE_NODECOUNT,
  NATIVE_RANDOM,
  NATIVE_GETLIMIT,
  NATIVE_GAMBLE,
  NATIVE_PRINT,
  NATIVE_CAR,
  NATIVE_CDR,
  NATIVE_CONS,
  NATIVE_PROGN,
  NATIVE_CRASH,
  NATIVE_EXCEPTION,
};

enum SpecialForm {
  SPECIAL_IF,
  SPECIAL_AND,
  SPECIAL_OR,
  SPECIAL_QUOTE,
  SPECIAL_LIMIT,
  SPECIAL_NOLIMIT,
  SPECIAL_DOTIMES,
  SPECIAL_REPEAT,
  SPECIAL_LAMBDA,
  SPECIAL_LET,
  SPECIAL_COMMA,
  SPECIAL_BACKQUOTE,
  SPECIAL_TRY,
  SPECIAL_DEBUG,
  SPECIAL_DEF,
  SPECIAL_CLOSURE,
  SPECIAL_SAFE,
};

// Some well known objects
extern Object * NIL;
extern Object * T;
extern Object * ERROR;
extern Object * QUOTE;
extern Object * IF;
extern Object * AND;
extern Object * OR;
extern Object * LIMIT;
extern Object * NOLIMIT;
extern Object * CRASH;
extern Object * EXCEPTION;
extern Object * GETLIMIT;
extern Object * GAMBLE;
extern Object * PLUS;
extern Object * TIMES;
extern Object * MOD;
extern Object * DIVIDE;
extern Object * MINUS;
extern Object * LESS;
extern Object * NOT;
extern Object * FUNCALL;
extern Object * LIST;
extern Object * ARRAY;
extern Object * MARRAY;
extern Object * AREF;
extern Object * MSET;
extern Object * CAR;
extern Object * CDR;
extern Object * CONS;
extern Object * PROGN;
extern Object * LENGTH;
extern Object * NODECOUNT;
extern Object * DOTIMES;
extern Object * RANDOM;
extern Object * LAMBDA;
extern Object * LET;
extern Object * SELF;
extern Object * DEBUG_LEVEL;
extern Object * COMMA;
extern Object * BACKQUOTE;
extern Object * TRY;
extern Object * DEF;
extern Object * CLOSURE;

// returns -1 if not a valid list
inline int64 ListLength(Object *o) {
  int64 ret = 0;
  while (1) {
    if (o == NIL) return ret;
    if (!IsCons(o)) return -1;
    ret++;
    o = o->Ref(1);
  }
}

inline bool IsList(Object *o) { return (ListLength(o) >= 0);}

// Make a List Object based on a vector of Object *s
// Used for reading, so we save things as we go
inline Object * MakeList(ThreadAllocator *A, vector<Object *> & v) {
  ObjectVectorSaver s_v(A, &v);
  Object * ret = NIL;
  ObjectSaver s_ret(A, &ret);
  for (int64 i = (int64)v.size() - 1; i >= 0; i--) {    
    ret = A->MakeArray(2, &v[i], &ret);
  }
  return ret;
}

// Initialize all the well known objects
void InitEnumObjects();

// Returns an empty string for failure or end of input
string ReadToken(istream &input);

// Read an object from a stream
Object * ReadObject(ThreadAllocator *a_, istream &input);

// Outputing an Object in a way it can be read back in
string ToString(Object *p);
ostream & operator << (ostream & ostr, Object *p);

// References into the marray that code compiles into
enum CodeInfo {
  ARITY,               // Arity of the code
  SHOULD_CACHE,
  //  NUM_CALLS,           // Number of times it's been called
  //  TOTAL_INSTRUCTIONS,  // Total #instructions executed 
  COMPILE_LOG,         // Compiling information
  CODE_INFO_MAX,
};

struct CodeStackFrame {
  Object ** return_ip_; // where do we return when we are done.
  uint64 cache_key_; // if we will be caching the execution - where? 
  Object * compiled_code_; // the compiled code we're running
  int64 start_num_instructions_executed_; // to compute running time
  Object ** function_in_stack_; // points to the running function.  Parameters follow.
  
};


// Used for an execution cache. 
// TODO: make thread safe. 
struct Cache : public AllocatorDependant {
  // a cell in the execution cache
  struct Cell {
    uint64 key_;      // a hash of the function and all the parameters
    Object *value_;   // the return value
  };

  Cell *data_; // the execution cache
  int64 size_;   // in cache cells
  int64 size_mask_;

  Cache(int64 lg_size) {
    G_ALLOC.AddDependant(this);
    size_ = (1 << lg_size);
    size_mask_ = size_ - 1;
    data_ = new Cell[size_];
    for (int64 i=0; i<size_; i++) data_[i].value_ = NULL;
  }
  ~Cache() {
    delete [] data_;
  }
  void Store(uint64 k, Object *v) {
    Cell & c_ref = data_[k & size_mask_];
    // if (c_ref.key_ - (uint64) c_ref.value_ == k) return;
    c_ref.key_ = k + (uint64) v;
    c_ref.value_ = v;
  }
  Object * Lookup(uint64 k) {
    const Cell &c = data_[k % size_];
    Object * v = c.value_;
    return (c.key_ - (uint64)v  == k) ? v : NULL;
  }
  int32 NumShards();
  void FlagReferences(int32 shard, Frontier *frontier);
  void ObjectsDeleted(int32 shard);
  void ClearSpace(int32 urgency);
};

extern Cache * G_CACHE;
  
class System;

struct Vinterpreter;

// Do a bunch of things that get interpretation working
void InitInterpret();

struct GlobalInterpreter : public AllocatorDependant {
  // maps from symbols to values
  // almost certainly want a lock around this. 
  hash_map<Object *, Object *, PointerHash<Object> > globals_;

  int32 NumShards() { return 1;}
  void FlagReferences(int32 shard, Frontier *frontier) {
    // cout << "GlobalInterpreter::FlagReferences" << endl;
    forall(run, globals_) 
      frontier->AddObject(run->second);
  }
  void ObjectsDeleted(int32 shard) {
    forall(run, globals_) {
      run->second = NewLocation(run->second);
      CHECK(run->second);
    }
  }
};
extern GlobalInterpreter * G_INTERP;



struct Vinterpreter :public AllocatorDependant {
  enum ExecState {
    STATE_SAFE,           // 
    STATE_RETURN,         //
    STATE_LIMIT_CALL,     //
    STATE_LIMIT,          // OldTimeLimit(), ValueStackSize()
    STATE_BIND,           // Symbol(), Value()
    STATE_SUBS,           // Code(), Position()
    STATE_IF,             // Code()
    STATE_AND,            // Code()
    STATE_OR,             // Code()
    STATE_LET,            // Code(), Symbol()
    STATE_DOTIMES_START,  // Code(), Symbol()
    STATE_DOTIMES_RUN,    // Max(), Current()
    STATE_DOTIMES_INFO,   // Code(), Symbol()
    STATE_REPEAT_START,   // Code(), Symbol()
    STATE_REPEAT_RUN,     // Max(), Current()
    STATE_CACHE,          // StartTime(), CacheKey()
    STATE_BACKQUOTE_SUBS, // Code(), Position()
    STATE_DEF, // Symbol()
  };

  struct ExecFrame {
    ExecState state_;
    Object * code_;
    Object * aux_;
    int64 & IntCode() { return *((int64*)(&code_));}
    int64 & IntAux() { return *((int64*)(&aux_));}
    uint64 & UintAux() { return *((uint64*)(&aux_));}
    Object *& Code() { return code_;}
    int64 & OldTimeLimit() { return IntCode();}    // STATE_LIMIT
    int64 & ValueStackSize() { return IntAux();}   // STATE_LIMIT, STATE_SAFE 
    Object *& Symbol() {return aux_;}              // STATE_BIND, STATE_LET
    Object *& OldValue() {return code_;}           // TODO: remove
    Object *& Value() {return code_;}           // STATE_BIND
    uint64 & Position() {return UintAux();}    // STATE_SUBS, STATE_AND, STATE_OR
    int64 & Current() { return IntCode();}
    int64 & Max() { return IntAux();}
    int64 & StartTime() { return IntCode();}
    uint64 & CacheKey() { return UintAux();}
    void Display(ostream & output);
  };

  StableVector<ExecFrame> exec_stack_;
  StableVector<Object *> value_stack_;
  Object ** var_hash_;
  ThreadAllocator *a_;
  System * system_;
  //  StableVector<Object *> array_stack_;
  RNG rng_;
  int64 clock_;
  int64 time_limit_;
  int64 last_uncachable_instruction_;

  void LoadFile(string fn, bool verbose);
  void ExecuteStream(istream &input, bool verbose);

  // returns success
  inline bool SetGlobal(Object *key, Object *value) {
    bool failure = false;
    pthread_mutex_lock(&G_LOCK);
    if (G_INTERP->globals_ % key) failure = true;
    else G_INTERP->globals_[key] = value;
    pthread_mutex_unlock(&G_LOCK);
    return !failure;
  }

  // returns NULL on failure
  inline Object * GetGlobal(Object *key) {
    Object ** look2 = G_INTERP->globals_ % key; 
    if (look2) return *look2; return NULL;
  }

  // Computed using the virtual start technique
  inline int64 Clock() { return clock_;}
  
  inline void SetClock(int64 clock) { clock_ = clock;}

  inline void AdvanceClock(uint64 delta) { clock_ += delta; }

  // instructions until the next limit
  int64 InstructionsRemaining() {
    return time_limit_ - clock_;
  }

  bool NearCapacity() { 
    return (value_stack_.NearCapacity(1000) || exec_stack_.NearCapacity(1000));
  }
  
  bool Overtime() { return (clock_ >= time_limit_); }
  
  // Accessing parameters from the outside
  Object * GetParameter(int32 i, int32 num) { 
    return value_stack_.end()[i-num];
  }

  Vinterpreter();
  void Display(ostream &output);

  /*
  // Simple changes to code
  Object * LimitedCode(Object *& code, int64 limit);
  Object * LambdadCode(Object*& code);
  Object * EvaledCode(Object *& code);
  */

  // part of AllocatorDependant
  int32 NumShards() { return 1;}
  void FlagReferences(int32 shard, Frontier *frontier);
  void ObjectsDeleted(int32 shard);

  // Figures out if any code is always constant valued
  // If so, returns the Object that is its value
  Object * ConstantValue(Object * code);
  
  void FailTimeLimit() {
  }
  void Reset() {
    value_stack_.clear();
    exec_stack_.clear();
  }
  Object * SafeExecute(Object *code_in, uint64 limit);

  void PushReturn();
  void PushSafe();
  /*  void PushStart(Object * code_in) {
    exec_stack_.push_back();
    exec_stack_.back().state_ = STATE_START;
    exec_stack_.back().Code() = code_in;
    } */
  void PushLimit(int64 limit) {
    exec_stack_.push_back();
    exec_stack_.back().state_ = STATE_LIMIT;
    exec_stack_.back().OldTimeLimit() = time_limit_;
    exec_stack_.back().ValueStackSize() = value_stack_.size();
    if (limit == -1) time_limit_ = LLONG_MAX;
    else time_limit_ = min(clock_ + limit, time_limit_);
  }
  /*void SetVar(Object * symbol, Object * value) {
    var_hash_[Hash(symbol) & kVarHashMask] = value;
    }*/
  Object * GetVar(Object * symbol) {
    ExecFrame * p = exec_stack_.end() - 1;
    while (1) {
      if (p < exec_stack_.begin()) return NIL;
      if (p->state_ == STATE_BIND) {
	if (p->Symbol() == symbol) return p->Value();
	if (p->Symbol() == SELF) return NIL;
      }
      p--;
    }
  }
  void Bind(Object * symbol, Object * value) {
    exec_stack_.push_back();
    exec_stack_.back().state_ = STATE_BIND;
    exec_stack_.back().Symbol() = symbol;
    exec_stack_.back().Value() = value;
  }
  void Unroll1() {
    ExecFrame & e = exec_stack_.back();
    /* if (e.state_ == STATE_BIND) {
      SetVar(e.Symbol(), e.OldValue());
      }*/
    if (e.state_ == STATE_LIMIT) {
      time_limit_ = e.OldTimeLimit();
    }
    exec_stack_.pop_back();
  }

};

// Access to T_INTERP the thread based allocator
// extern __thread Vinterpreter * T_INTERP;

class System {
 public:
  virtual Object* Syscall (int32 num_parameters) = 0;
  virtual bool IsNativeMethod(Object * name) = 0;
  virtual void ForgetSince(int64 old_clock) {}
  virtual ~System(){}
};

int interpret_main();

// abstract tester class
struct Tester {
  // returns a non-negative utility delta
  virtual double Test(Object *&code, Vinterpreter *interp_, bool update) = 0;
  virtual Object * Data(Object *&param, ThreadAllocator *a) { return NULL; }
  virtual ~Tester() {};
};

#endif
